1. Technical Field
This invention relates to computerized data processing, and more particularly to the management of computer system resources such as buffers in systems where multiple processes are executing concurrently.
2. Technical Background
Multiprocessing: A computer program consists of a sequence of computer instructions and can be executed as a single sequence of instructions or as a set of independent sequences of instructions called "processes". To acquire the use of a computer's resources, the program usually issues requests, called "system calls", to the computer's "operating system". The operating system is a program that manages the use of a computer's resources, such as computer memory or hardware devices. Resources requested by a program are reserved for its exclusive use and are not available for reuse until each is returned to the control of the operating system ("released"). Since system resources are limited and system calls relatively expensive to perform, programs (especially high-volume or high-performance programs) use them in a controlled fashion.
Programs and processes may operate in a number of computer environments. In a "multiprogramming" environment, the execution of two or more programs or processes may be interleaved on one processor. In such a case, a process being executed may be "interrupted"; the computer will stop executing the process and do other work, such as executing another process. It may be some time before the next instruction in the interrupted process is executed. Some processes in this environment may be "disabled" for interrupts. Such processes will not be interrupted and will execute from beginning to end as a sequence.
In a "multiprocessing" environment, the computer consists of more than one processor and each processor may be executing programs or processes in parallel. For example, if a program has two processes, then both may be executing at the same time in a multiprocessing environment. Each processor in a multiprocessor may also be multiprogramming.
Thus, in a multiprocessing environment a process' actions may be interleaved with those of other processes. That process is then said to be executing "concurrently" with the other processes. Also, more than one process may be executing at exactly the same time. Processes executing at the same time on different processors are said to be executing "in parallel".
Serialization: Processes executing concurrently or in parallel may be writing data simultaneously into the same piece of storage, so that one process will destroy what another has written. To prevent errors of this kind, such processes must use one or more "serialization mechanisms" to "serialize" the processes. These mechanisms, some standard and well-known, allow the program to complete critical actions as if they were accomplished by an uninterrupted sequence of instructions, even though the sequence may, in fact, be interrupted at any time. Also, they allow a program to serialize access to a resource so that it is used by only one process at a time. For our purposes, we distinguish between "intrinsic" serialization mechanisms and "extrinsic" serialization mechanisms.
Intrinsic serialization mechanisms are those which involve only "atomic instructions", such as the IBM 370 Compare-and-Swap (CS) or Compare-Double-and-Swap (CDS) instructions. Atomic instructions are computer hardware instructions that are guaranteed to be indivisible. A process executing such an instruction is assured that it can complete the instruction without interference from other processes. Compare-and-Swap, for example, allows a process to update a word of storage safely. The instruction allows a program to note the expected contents of a word in storage and to request that the storage be altered only if the expected contents of the storage matches the current contents when the instruction is executed. The comparison (compare) and alteration (swap) are indivisible actions in the sense that once a process has performed the "compare", no other process can perform the alteration until the associated "swap" is done. The description of these instruction, as well as sample coded applications, can be found in IBM System/370 Extended Architecture Principles of Operation (Publication Number SA22-7085).
Latches: All other serialization mechanisms are said to be "extrinsic". Two basic examples of such are the "spin latch" and the "suspend latch". They involve having a single shared latch variable that is initially set to some null value. To perform an action that is protected by the latch, a process must first "acquire" the latch by successfully setting the latch variable to a non-null value. If the latch variable has already been acquired by another process, the requesting process must wait.
A spin latch is one that causes the requesting process (and processor) to test the variable continously as it waits for the latch to be "released". While this testing takes place the processor is said to be "busy waiting", and cannot do anything else. This type of latch should generally be avoided as it wastes processor time.
A suspend latch, on the other hand, does not require the process to busy wait for the latch if it is already held. Instead, the process "suspends", giving up the processor, until it is awakened ("resumed") by another process (e.g., the operating system) when the latch is available. Although this method is preferable to spin latches, it is nevertheless used with care because of the system overhead associated with keeping track of the suspension and resumption of the requesting process.
For high-performance programs operating in a multiprocessing environment, the choice of serialization mechanisms can be critical. It is useful to divide a program's functions into those which are "mainline" and those which are not. Mainline functions are the essence of the program, while non-mainline functions are those ancilliary actions which facilitate or complement the mainline actions. In a high-performance program, the mainline actions are typically executed repetitively or are time-critical, so that it is essential that actions which are expensive in terms of CPU time or CPU resources be avoided or moved to non-mainline functions. In general, extrinsic serialization mechanisms in the mainline can be expensive and should be avoided.
Resources and Buffers: A program typically performs one or more specialized repetitive functions and may require resources to perform those functions or to represent objects associated with them. The program may acquire storage for such resources, and collect that storage together into what is commonly called a "resource pool". In creating resource pools, programs in multiprocessing environments must be able to serialize access to the individual resources in the pool. Furthermore, programs usually need to dynamically "expand" and "contract" the pool--i.e. to increase or decrease the number of resources in the pool.
The following discussion describes the need for resource pooling in a specific example and also discusses some of the issues that arise in managing the pool. Suppose a program ("the receiver") gets data that is generated by another program ("the sender"). The receiver may acquire a piece of storage to hold data from the sender. Each piece of computer storage used for this purpose is usually called a "buffer", and is a type of resource as that term is used herein.
Data is placed into buffers as it arrives, and held there until it can be used. When the receiver has used the data in the buffer, it can receive more data for processing. Once used, the buffer is available for reuse in receiving new data.
If data can be received faster than can be processed, a number of buffers may be acquired ahead of time. The program usually organizes the buffers into a logical structure called a "buffer pool"--i.e. a resource pool. In a multiprocessing environment, the buffer pool can be used by any of the processes belonging to the program and the program must control the way in which its processes use the buffers in the buffer pool. Usually, the program will provide a way for processes to "get" and "free" buffers from the buffer pool in such a way that no two processes will get the same buffer at the same time.
In addition to controlling access to the buffers in the buffer pool, the program must also decide how many buffers to include in the buffer pool. If too few buffers are included in the buffer pool, the program may run out of buffers. The programmer may attempt to avoid this problem by determining the maximum number of buffers the program is expected to use. If the program usually only uses a small percentage of that number, then by allocating a buffer pool of the maximum size the program unnecessarily reserves computer storage that could be used instead by other programs. However, if the expected maximum size of the buffer pool is too small, the program will run out of buffers.
If the program runs out of buffers when one of its processes has data to store, the process cannot function normally and the program must take immediate action. The program might, for example, terminate execution. This "solution" is unacceptable in the great majority of cases, where continuing program execution is vital to the operation of a company or other enterprise. The program might instead throw away the process' data. However, if the data cannot be regenerated or reproduced, or is otherwise vital to the enterprise, then this solution too is unacceptable.
The program could wait until a buffer becomes available for storage. This might done where another process is using data from a buffer in parallel with the process needing the buffer for storage, and is expected to finish soon, freeing it. If this approach is taken, all processes needing buffers for storage will have to wait until the termination of a process using data from a buffer. However, if those processes using data are themselves waiting for action by processes awaiting storage buffers, the program will be "deadlocked"--unable to perform further work. For this reason, waiting for other processes to free up buffers for reuse is not acceptable.